//给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可
//能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。 
//
// 
//
// 示例 1: 
//
// 输入: 12258
//输出: 5
//解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi" 
//
// 
//
// 提示： 
//
// 
// 0 <= num < 2³¹ 
// 
// Related Topics 字符串 动态规划 👍 456 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//Java：把数字翻译成字符串
public class BaShuZiFanYiChengZiFuChuanLcof {
    public static void main(String[] args) {
        Solution solution = new BaShuZiFanYiChengZiFuChuanLcof().new Solution();
        // TO TEST
        System.out.println(solution.translateNum(12258));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int translateNum(int num) {
            // 1、将num转换成字符串
            String numStr = String.valueOf(num);
            int nlen = numStr.length();
            int[] dt = new int[nlen + 1];
            dt[0] = dt[1] = 1;
            for (int i = 2; i < dt.length; i++) {
                // 看数据是否可翻译
                String subStr = numStr.substring(i - 2, i);
                // dt[i] = dt[i-1] + dt[i-2];
                int subInt = Integer.parseInt(subStr);
                if (subInt >= 10 && subInt <= 25) {
                    dt[i] = dt[i-1] + dt[i-2];
                } else {
                    dt[i] = dt[i-1];
                }
                // dt[i] = dt[i-1];
            }
            return dt[nlen];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
